package LeetCode.CountingSort;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author : LdLtd
 * @Date : 2023/9/12
 * @Description:计数排序
 */
public class CountingSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[]ar=new int[]{1,3,2,4,5};
//        for (int i = 0; i < 5; i++) {
//            ar[i]=sc.nextInt();
//        }

        /*1.首先找出数据中最大的一个数
        * 2.新建一个数组，长度为最大的数+1
        * 3.对原数组的每一个数的出现次数进行计数
        * 4对每个数字进行累计
        * 5.根据累计的次数，输出到原数组*/
        int len =findMax(ar);
        int [] nums=new int[len+1];
        //计数
        for (int i = 0; i < ar.length; i++) {
            nums[ar[i]]++;
        }
        //统计计数累计
        for (int i = 1; i <nums.length ; i++) {
            nums[i]+=nums[i-1];
        }
        //临时数组保存答案
        int[]res=new int[ar.length];
        for (int i = 0; i < ar.length; i++) {
            res[nums[ar[i]]-1]=ar[i];
            nums[ar[i]]--;
        }
        //放到原数组
        System.arraycopy(res,0,ar,0,ar.length);
        Arrays.stream(ar).forEach(System.out::print);

    }
    public static int findMax(int[] nums){
        int res=0;
        for (int i = 0; i < nums.length; i++) {
            res=Math.max(res,nums[i]);
        }
        return res;
    }
}
